#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <complex>
#include <cstdio>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<VI> VVI;
// BEGIN CUT HERE
// END CUT HERE
// BEGIN CUT HERE
typedef pair<VI,int> PII;
typedef vector<PII> VPII;
#define X first
#define Y second
#define mp make_pair
// BEGIN CUT HERE
// END CUT HERE
// BEGIN CUT HERE
#define two(x) (1<<(x))
#define twoll(x) ((long long)1<<(x))
#define contain(s,x) (((s)&two(x))!=0)
#define containll(s,x) (((s)&twoll(x))!=0)
// BEGIN CUT HERE
// END CUT HERE
// BEGIN CUT HERE
#define db(a) cout << #a << "=" << a << " "
#define dbn cout << endl
#define dbs(str) cout << str
template<class T> void print(vector<T> v) { cout << "["; if (v.size()) cout << v[0]; for (unsigned i = 1; i < v.size(); i++) cout << ", " << v[i];cout << "]\n"; }
template<class T> void print(vector<vector<T> > v) { cout << "[ ---\n"; if (v.size()) cout << " ", print(v[0]); for (unsigned i = 1; i < v.size(); i++) cout << " ", print(v[i]); cout << "--- ]\n"; }
template<class T1, class T2> void print(pair<T1,T2> p) { cout << "{" << p.first << ", " << p.second << "}"; }
template<class T1, class T2> void print(vector<pair<T1,T2> > v) { cout << "["; if (v.size()) print(v[0]); for (unsigned i = 1; i < v.size(); i++) cout << ", ", print(v[i]);cout << "]\n"; }
template<class T> inline T sqr(T x) { return x*x; }
// BEGIN CUT HERE
// END CUT HERE
// BEGIN CUT HERE
template<class T> inline int chkmin(T& a, T b) { if (a>b) {a=b; return 1;} return 0; }
template<class T> inline int chkmax(T& a, T b) { if (a<b) {a=b; return 1;} return 0; }
// BEGIN CUT HERE
// END CUT HERE
// BEGIN CUT HERE
//string STR(long long n) { char tmp[20]; lltoa(n,tmp,10); return string(tmp); }
//long long LL(string s) { return atoll(s.c_str()); }
template <class Ty, class Tx> Ty to(const Tx &x) { Ty y; stringstream ss; ss<<x; ss>>y; return y; }
// BEGIN CUT HERE
// END CUT HERE
const int INF = 1000000007;
const double EPS = 1e-10;
// BEGIN CUT HERE
#define TESTCASE 
// END CUT HERE

template <class T>
vector<vector<T> > Warshall_Floyd(vector<vector<T> > adj)
{
	int n = adj.size();
	for (int k = 0; k < n; ++k)
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				adj[i][j] = min(adj[i][j],adj[i][k]+adj[k][j]);
	return adj;
}

struct PowerOutage
{
	int estimateTimeOut(vector <int> from, vector <int> to, vector <int> len)
	{
		VVI G;
		int sz = max(*max_element(all(from)), *max_element(all(to))) + 1;
		G.resize(sz, VI(sz, INF));
		for (int i = 0; i < from.size(); ++i)
		{
			G[from[i]][to[i]] = G[to[i]][from[i]] = len[i];
			G[i][i] = 0;
		}
		G = Warshall_Floyd(G);
		for (int i = 0; i < G.size(); ++i)
			replace(all(G[i]), INF, 0);

		return accumulate(all(len), 0) * 2 - *max_element(all(G[0]));
	}
};
// BEGIN CUT HERE
namespace moj_harness {
int run_test_case(int);
void run_test(int casenum = -1, bool quiet = false) {
	if ( casenum != -1 ) {
		if ( run_test_case( casenum ) == -1 && !quiet )
			cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
		return;
	}

	int correct = 0, total = 0;
	for ( int i=0;; ++i ) {
		int x = run_test_case(i);
		if ( x == -1 ) {
			if ( i >= 100 ) break;
			continue;
		}
		correct += x;
		++total;
	}

	if ( total == 0 ) {
		cerr << "No test cases run." << endl;
	} else if ( correct < total ) {
		cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
	} else {
		cerr << "All " << total << " tests passed!" << endl;
	}
}

int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) {
	cerr << "Example " << casenum << "... ";

	string verdict;
	vector<string> info;
	char buf[100];

	if (elapsed > CLOCKS_PER_SEC / 200) {
		sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
		info.push_back(buf);
	}

	if ( expected == received ) {
		verdict = "PASSED";
	} else {
		verdict = "FAILED";
	}

	cerr << verdict;
	if (!info.empty()) {
		cerr << " (";
		for (int i=0; i<(int)info.size(); ++i) {
			if (i > 0) cerr << ", ";
			cerr << info[i];
		}
		cerr << ")";
	}
	cerr << endl;

	if (verdict == "FAILED") {
		cerr << "    Expected: " << expected << endl;
		cerr << "    Received: " << received << endl;
	}

	return verdict == "PASSED";
}

int run_test_case( int casenum ) {
	switch( casenum ) {
	case 0: {
		int fromJunction[]        = {0};
		int toJunction[]          = {1};
		int ductLength[]          = {10};
		int expected__            = 10;

		clock_t start__           = clock();
		int received__            = PowerOutage().estimateTimeOut( vector <int>( fromJunction, fromJunction + ( sizeof fromJunction / sizeof fromJunction[0] ) ), vector <int>( toJunction, toJunction + ( sizeof toJunction / sizeof toJunction[0] ) ), vector <int>( ductLength, ductLength + ( sizeof ductLength / sizeof ductLength[0] ) ) );
		return verify_case( casenum, expected__, received__, clock()-start__ );
	}
	case 1: {
		int fromJunction[]        = {0,1,0};
		int toJunction[]          = {1,2,3};
		int ductLength[]          = {10,10,10};
		int expected__            = 40;

		clock_t start__           = clock();
		int received__            = PowerOutage().estimateTimeOut( vector <int>( fromJunction, fromJunction + ( sizeof fromJunction / sizeof fromJunction[0] ) ), vector <int>( toJunction, toJunction + ( sizeof toJunction / sizeof toJunction[0] ) ), vector <int>( ductLength, ductLength + ( sizeof ductLength / sizeof ductLength[0] ) ) );
		return verify_case( casenum, expected__, received__, clock()-start__ );
	}
	case 2: {
		int fromJunction[]        = {0,0,0,1,4};
		int toJunction[]          = {1,3,4,2,5};
		int ductLength[]          = {10,10,100,10,5};
		int expected__            = 165;

		clock_t start__           = clock();
		int received__            = PowerOutage().estimateTimeOut( vector <int>( fromJunction, fromJunction + ( sizeof fromJunction / sizeof fromJunction[0] ) ), vector <int>( toJunction, toJunction + ( sizeof toJunction / sizeof toJunction[0] ) ), vector <int>( ductLength, ductLength + ( sizeof ductLength / sizeof ductLength[0] ) ) );
		return verify_case( casenum, expected__, received__, clock()-start__ );
	}
	case 3: {
		int fromJunction[]        = {0,0,0,1,4,4,6,7,7,7,20};
		int toJunction[]          = {1,3,4,2,5,6,7,20,9,10,31};
		int ductLength[]          = {10,10,100,10,5,1,1,100,1,1,5};
		int expected__            = 281;

		clock_t start__           = clock();
		int received__            = PowerOutage().estimateTimeOut( vector <int>( fromJunction, fromJunction + ( sizeof fromJunction / sizeof fromJunction[0] ) ), vector <int>( toJunction, toJunction + ( sizeof toJunction / sizeof toJunction[0] ) ), vector <int>( ductLength, ductLength + ( sizeof ductLength / sizeof ductLength[0] ) ) );
		return verify_case( casenum, expected__, received__, clock()-start__ );
	}
	case 4: {
		int fromJunction[]        = {0,0,0,0,0};
		int toJunction[]          = {1,2,3,4,5};
		int ductLength[]          = {100,200,300,400,500};
		int expected__            = 2500;

		clock_t start__           = clock();
		int received__            = PowerOutage().estimateTimeOut( vector <int>( fromJunction, fromJunction + ( sizeof fromJunction / sizeof fromJunction[0] ) ), vector <int>( toJunction, toJunction + ( sizeof toJunction / sizeof toJunction[0] ) ), vector <int>( ductLength, ductLength + ( sizeof ductLength / sizeof ductLength[0] ) ) );
		return verify_case( casenum, expected__, received__, clock()-start__ );
	}

	// custom cases

	/*      case 5: {
			int fromJunction[]        = ;
			int toJunction[]          = ;
			int ductLength[]          = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = PowerOutage().estimateTimeOut( vector <int>( fromJunction, fromJunction + ( sizeof fromJunction / sizeof fromJunction[0] ) ), vector <int>( toJunction, toJunction + ( sizeof toJunction / sizeof toJunction[0] ) ), vector <int>( ductLength, ductLength + ( sizeof ductLength / sizeof ductLength[0] ) ) );
			return verify_case( casenum, expected__, received__, clock()-start__ );
		}*/
	/*      case 6: {
			int fromJunction[]        = ;
			int toJunction[]          = ;
			int ductLength[]          = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = PowerOutage().estimateTimeOut( vector <int>( fromJunction, fromJunction + ( sizeof fromJunction / sizeof fromJunction[0] ) ), vector <int>( toJunction, toJunction + ( sizeof toJunction / sizeof toJunction[0] ) ), vector <int>( ductLength, ductLength + ( sizeof ductLength / sizeof ductLength[0] ) ) );
			return verify_case( casenum, expected__, received__, clock()-start__ );
		}*/
	/*      case 7: {
			int fromJunction[]        = ;
			int toJunction[]          = ;
			int ductLength[]          = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = PowerOutage().estimateTimeOut( vector <int>( fromJunction, fromJunction + ( sizeof fromJunction / sizeof fromJunction[0] ) ), vector <int>( toJunction, toJunction + ( sizeof toJunction / sizeof toJunction[0] ) ), vector <int>( ductLength, ductLength + ( sizeof ductLength / sizeof ductLength[0] ) ) );
			return verify_case( casenum, expected__, received__, clock()-start__ );
		}*/
	default:
		return -1;
	}
}
}


int main(int argc, char *argv[]) {
	freopen("DATA.in", "rt", stdin);
	freopen("DATA.ou", "wt", stdout);

	if (argc == 1) {
		moj_harness::run_test(TESTCASE);
	} else {
		for (int i=1; i<argc; ++i)
			moj_harness::run_test(atoi(argv[i]));
	}

	return 0;
}
// END CUT HERE
